package everyday;

/**
 * @author zhangmin
 * @create 2022-04-29 11:07
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 * 测试用例的答案是一个 32-位 整数。
 * 子数组 是数组的连续子序列。
 *
 * 思路：
 * dp[i][0]表示以i为结尾的子数组乘积最小值,最小值有可能是前一位的最小值和当前乘、也可能单独成一个数组、也可能是前一个的最大值和当前乘
 * dp[i][0]= Math.min(dp[i-1][0]*nums[i],Math.min(nums[i],dp[i-1][1]*nums[i]));
 * dp[i][1]表示以i为结尾的子数组乘积最大值，最da值有可能是前一位的最小值和当前乘、也可能单独成一个数组、也可能是前一个的最大值和当前乘
 * dp[i][1]=Math.max(dp[i-1][1]*nums[i],Math.max(nums[i],dp[i-1][0]*nums[i]));
 *
 */
public class maxProduct152 {
    public int maxProduct(int[] nums) {
        int n=nums.length;
        int[][] dp=new int[n][2];
        dp[0][0]=nums[0];
        dp[0][1]=nums[0];
        int res=nums[0];
        for (int i = 1; i < n; i++) {
            dp[i][0]= Math.min(dp[i-1][0]*nums[i],Math.min(nums[i],dp[i-1][1]*nums[i]));
            dp[i][1]=Math.max(dp[i-1][1]*nums[i],Math.max(nums[i],dp[i-1][0]*nums[i]));
            res=Math.max(res,dp[i][1]);
        }
        return res;
    }
}
